{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #不同路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: uniquePaths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个机器人位于一个 <code>m x n</code><em>&nbsp;</em>网格的左上角 （起始点在下图中标记为 &ldquo;Start&rdquo; ）。</p>\n",
    "\n",
    "<p>机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 &ldquo;Finish&rdquo; ）。</p>\n",
    "\n",
    "<p>问总共有多少条不同的路径？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 3, n = 7\n",
    "<strong>输出：</strong>28</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 3, n = 2\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "从左上角开始，总共有 3 条路径可以到达右下角。\n",
    "1. 向右 -&gt; 向下 -&gt; 向下\n",
    "2. 向下 -&gt; 向下 -&gt; 向右\n",
    "3. 向下 -&gt; 向右 -&gt; 向下\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 7, n = 3\n",
    "<strong>输出：</strong>28\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 3, n = 3\n",
    "<strong>输出：</strong>6</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 100</code></li>\n",
    "\t<li>题目数据保证答案小于等于 <code>2 * 10<sup>9</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 62&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/unique-paths/\">https://leetcode-cn.com/problems/unique-paths/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [2AoeFn](https://leetcode.cn/problems/2AoeFn/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [2AoeFn](https://leetcode.cn/problems/2AoeFn/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n7', '3\\n2', '7\\n3', '3\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        d=[1]*n\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                d[j]=d[j]+d[j-1]\n",
    "        return d[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        self.hashmap={}\n",
    "        \n",
    "        def path(goal:list,m:int,n:int):\n",
    "            if goal==[0,0]:\n",
    "                return 1\n",
    "            elif 0<=goal[0]<=m-1 and 0<=goal[1]<=n-1:\n",
    "                a=[goal[0]-1,goal[1]]\n",
    "                b=[goal[0],goal[1]-1]\n",
    "                if str(a) in self.hashmap:\n",
    "                    ans_a = self.hashmap[str(a)]\n",
    "                else:\n",
    "                    ans_a = path(a,m,n)\n",
    "                    self.hashmap[str(a)] = ans_a\n",
    "\n",
    "                if str(b) in self.hashmap:\n",
    "                    ans_b = self.hashmap[str(b)]\n",
    "                else:\n",
    "                    ans_b = path(b,m,n)\n",
    "                    self.hashmap[str(b)] = ans_b\n",
    "                return ans_a+ans_b\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        return path([m-1,n-1],m,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        self.hashmap={}\n",
    "        \n",
    "        def path(goal:list,m:int,n:int):\n",
    "            if goal==[0,0]:\n",
    "                return 1\n",
    "            elif 0<=goal[0]<=m-1 and 0<=goal[1]<=n-1:\n",
    "                a=[goal[0]-1,goal[1]]\n",
    "                b=[goal[0],goal[1]-1]\n",
    "                if str(a) in self.hashmap:\n",
    "                    ans_a = self.hashmap[str(a)]\n",
    "                else:\n",
    "                    ans_a = path(a,m,n)\n",
    "                    self.hashmap[str(a)] = ans_a\n",
    "\n",
    "                if str(b) in self.hashmap:\n",
    "                    ans_b = self.hashmap[str(b)]\n",
    "                else:\n",
    "                    ans_b = path(b,m,n)\n",
    "                    self.hashmap[str(b)] = ans_b\n",
    "                return ans_a+ans_b\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        return path([m-1,n-1],m,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        self.hashmap={}\n",
    "        for i in range(m):\n",
    "            self.hashmap[str([i,0])]=1\n",
    "            #self.hashmap[str([i,n-1])]=1\n",
    "        for i in range(n):\n",
    "            self.hashmap[str([0,i])]=1\n",
    "            #self.hashmap[str([m-1,i])]=1\n",
    "\n",
    "        def path(goal:list,m:int,n:int):\n",
    "            if goal==[0,0]:\n",
    "                return 1\n",
    "            elif 0<=goal[0]<=m-1 and 0<=goal[1]<=n-1:\n",
    "                a=[goal[0]-1,goal[1]]\n",
    "                b=[goal[0],goal[1]-1]\n",
    "                if str(a) in self.hashmap:\n",
    "                    ans_a = self.hashmap[str(a)]\n",
    "                else:\n",
    "                    ans_a = path(a,m,n)\n",
    "                    self.hashmap[str(a)] = ans_a\n",
    "\n",
    "                if str(b) in self.hashmap:\n",
    "                    ans_b = self.hashmap[str(b)]\n",
    "                else:\n",
    "                    ans_b = path(b,m,n)\n",
    "                    self.hashmap[str(b)] = ans_b\n",
    "                return ans_a+ans_b\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        return path([m-1,n-1],m,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j+1 < n:dp[i][j+1]+=dp[i][j]\n",
    "                if i+1 < m:dp[i+1][j]+=dp[i][j]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        grid = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or j == 0:\n",
    "                    grid[i][j] = 1\n",
    "                else:\n",
    "                    grid[i][j] = grid[i - 1][j] + grid[i][j - 1]\n",
    "        return grid[m - 1][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[1 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i-1][j]+dp[i][j-1]\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        return math.comb(m + n - 2, min(m, n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[1 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            dp[i][0] = 1\n",
    "        for j in range(n):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(m):\n",
    "            dp[i][0] = 1\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j]\n",
    "        return dp[m - 1][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[0] * (m+1) for _ in range(n+1)]\n",
    "        dp[1][1] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1):\n",
    "                if i == j == 1:\n",
    "                    continue\n",
    "                dp[i][j] = dp[i][j-1] + dp[i-1][j]\n",
    "        return dp[n][m]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[1 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i-1][j]+dp[i][j-1]\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp=[[0]*n for _ in range(m)]\n",
    "        for i in range(n):\n",
    "            dp[0][i]=1\n",
    "        for j in range(1,m):\n",
    "            dp[j][0]=1\n",
    "        for a in range(1,m):\n",
    "            for b in range(1,n):\n",
    "                dp[a][b]=dp[a-1][b]+dp[a][b-1]\n",
    "        return dp[m-1][n-1]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        if m == 1 or n == 1:\n",
    "            return 1\n",
    "            \n",
    "        matrix = [[1 for _ in range(n)] for _ in range(m)]\n",
    "        for r in range(1, m):\n",
    "            for c in range(1, n):\n",
    "                matrix[r][c] = matrix[r - 1][c] + matrix[r][c - 1]\n",
    "        \n",
    "        return matrix[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "       # 初始化一个 m 行 n 列的二维数组\n",
    "        dp = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]\n",
    "        # 从 dp[1][1] 开始逐行计算，每个位置的路径数等于左侧和上方位置的路径数之和\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]\n",
    "        # 返回右下角位置的路径数\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        return comb(m+n-2,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[1 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j] = dp[i-1][j]+dp[i][j-1]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        # 动态规划代码\n",
    "        # dp = [[1 for _ in range(n)] for _ in range(m)]\n",
    "        # for i in range(1, m):\n",
    "        #     for j in range(1, n):\n",
    "        #         dp[i][j] = dp[i-1][j]+dp[i][j-1]\n",
    "        # return dp[-1][-1]\n",
    "        \n",
    "        # 官方思路优化后代码\n",
    "        dp=list()\n",
    "        for i in range(n):\n",
    "            dp.append(1)\n",
    "        for i in range(m-1):\n",
    "            for j in range(1,n):\n",
    "                dp[j]=dp[j]+dp[j-1]\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j+1 < n:dp[i][j+1]+=dp[i][j]\n",
    "                if i+1 < m:dp[i+1][j]+=dp[i][j]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        def comb(n: int, k: int) -> int:\n",
    "            res = 1\n",
    "            for i in range(1, k + 1):\n",
    "                res = res * (n - i + 1) // i\n",
    "            return res\n",
    "        return comb(n + m - 2, m - 1)\n",
    "        '''\n",
    "        return int(math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1))\n",
    "        '''\n",
    "        '''\n",
    "        cur = [1] * n\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                cur[j] += cur[j-1]\n",
    "        return cur[-1]\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j+1 < n:dp[i][j+1]+=dp[i][j]\n",
    "                if i+1 < m:dp[i+1][j]+=dp[i][j]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        nums = [[0] * n for _ in range(m)]\n",
    "        nums[0][0] = 1\n",
    "        for x in range(m):\n",
    "            nums[x][0] = 1\n",
    "        for y in range(1, n):\n",
    "            nums[0][y] = 1\n",
    "        for x in range(1, m):\n",
    "            for y in range(1, n):\n",
    "                nums[x][y] = nums[x - 1][y] + nums[x][y - 1]\n",
    "        return nums[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        def fa(n):\n",
    "            if n == 1 or n == 0:\n",
    "                return 1\n",
    "            else:\n",
    "                return n*fa(n-1)\n",
    "        return int(fa(n+m-2)/(fa(n-1)*fa(m-1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        mat = [[1]*n]*m\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0:\n",
    "                    mat[i][j] = 1\n",
    "                elif j == 0:\n",
    "                    mat[i][j] = 1\n",
    "                else:\n",
    "                    mat[i][j] = mat[i-1][j] + mat[i][j-1]\n",
    "        return mat[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        # dp = [[1 for _ in range(n)] for _ in range(m)]\n",
    "        # for i in range(1, m):\n",
    "        #     for j in range(1, n):\n",
    "        #         dp[i][j] = dp[i-1][j]+dp[i][j-1]\n",
    "        # return dp[-1][-1]\n",
    "        dp=list()\n",
    "        for i in range(n):\n",
    "            dp.append(1)\n",
    "        for i in range(m-1):\n",
    "            for j in range(1,n):\n",
    "                dp[j]=dp[j]+dp[j-1]\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        f=[[1]*n]+[[1]+[0]*n for _ in range(m-1)]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                f[i][j]=f[i-1][j]+f[i][j-1]\n",
    "        return f[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[1 for tmp in range(n)]for tmp in range(m)]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[m-1][n-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = []\n",
    "        for i in range(m):\n",
    "            dp.append([0]*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or j == 0:\n",
    "                    dp[i][j] = 1\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        return math.comb(m+n-2,m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        return comb(m-1+n-1,m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        return comb(m + n - 2, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        if m == 1 or n == 1:\n",
    "            return 1\n",
    "        dp=[1]*n\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[j]=dp[j]+dp[j-1]\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[1] * n for _ in range(m)]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        m,n = n, m\n",
    "        tab = [[0 for i in range(m)] for j in range(n)]\n",
    "        for i in range(n):\n",
    "            tab[i][0] = 1\n",
    "        for j in range(m):\n",
    "            tab[0][j] = 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                tab[i][j] = tab[i-1][j] + tab[i][j-1]\n",
    "        return tab[n-1][m-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        nums=m-1+n-1\n",
    "        return comb(nums,m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        # 动态规划代码\n",
    "        # dp = [[1 for _ in range(n)] for _ in range(m)]\n",
    "        # for i in range(1, m):\n",
    "        #     for j in range(1, n):\n",
    "        #         dp[i][j] = dp[i-1][j]+dp[i][j-1]\n",
    "        # return dp[-1][-1]\n",
    "        \n",
    "        # 官方思路优化后代码\n",
    "        dp=list()\n",
    "        for i in range(n):\n",
    "            dp.append(1)\n",
    "        for i in range(m-1):\n",
    "            for j in range(1,n):\n",
    "                dp[j]=dp[j]+dp[j-1]\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[1 for i in range(n)] for j in range(m)]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        f = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m -1)]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                f[i][j] = f[i - 1][j] + f[i][j - 1]\n",
    "\n",
    "        return f[m - 1][n - 1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        def fa(n):\n",
    "            if n == 1 or n == 0:\n",
    "                return 1\n",
    "            else:\n",
    "                return n*fa(n-1)\n",
    "        return int(fa(n+m-2)/(fa(n-1)*fa(m-1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            dp[i][0] = 1\n",
    "        for j in range(n):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        #dp[i][j]是机器人到达i-1,j-1坐标的路径种类\n",
    "        dp=[[0]*n for _ in range(0,m)]\n",
    "        dp[0][0]=0 \n",
    "        for i in range(0,n):\n",
    "            dp[0][i]=1\n",
    "        for i in range(0,m):\n",
    "            dp[i][0]=1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j]=dp[i-1][j]+dp[i][j-1]\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            dp[i][0] = 1\n",
    "        for j in range(n):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        # dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        if m == 1 and n == 1:\n",
    "            return 1\n",
    "        for a in range(1,n):\n",
    "            dp[0][a] = 1\n",
    "        for b in range(1,m):\n",
    "            dp[b][0] = 1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        # return c82\n",
    "        a = m + n - 2\n",
    "        b = min(m,n) - 1\n",
    "        ret = 1\n",
    "        for i in range(min(m,n) - 1):\n",
    "            ret *= a\n",
    "            a -= 1\n",
    "        for i in range(min(m,n) - 1):\n",
    "            ret /= b\n",
    "            b -= 1\n",
    "        return int(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[1] * n] + [[1] + [0] * (n-1) for _ in range(m)] \n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[0 for i in range(n)] for j in range(m)]\n",
    "\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, m):\n",
    "            dp[i][0] = 1\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            dp[0][i] = 1\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        f=[[1]*n for _ in range(m)]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                    f[i][j]=f[i-1][j]+f[i][j-1]\n",
    "\n",
    "        return f[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [ [0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            dp[i][0] = 1\n",
    "        for j in range(n):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        from math import comb \n",
    "        return comb(m + n - 2, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        # 先全部初始化为1\n",
    "        dp = [[1 for _ in range(n)]for _ in range(m)]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "      self.cache = {}\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "      if (m,n) in self.cache:\n",
    "        return self.cache[(m,n)]\n",
    "      if m < 1 or n < 1:\n",
    "        return 0\n",
    "      if m == 1 or n == 1:\n",
    "        result = 1\n",
    "      else:\n",
    "        result = self.uniquePaths(m-1,n) + self.uniquePaths(m,n-1)\n",
    "      \n",
    "      self.cache[(m,n)] = result\n",
    "      return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            res[i][0] = 1\n",
    "        for i in range(n):\n",
    "            res[0][i] = 1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                res[i][j] = res[i-1][j]+res[i][j-1]\n",
    "        return res[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        # 一直向右\n",
    "        for i in range(n):\n",
    "            dp[0][i] = 1\n",
    "        for j in range(m):\n",
    "            dp[j][0] = 1\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i][j-1] + dp[i-1][j]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@functools.lru_cache()\n",
    "def dfs(cur_m,cur_n,m,n):\n",
    "    if cur_m > m or cur_n > n:\n",
    "        return 0\n",
    "    if cur_m == m and cur_n==n:\n",
    "        return 1\n",
    "    return dfs(cur_m+1,cur_n,m,n) + dfs(cur_m,cur_n+1,m,n)\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        return dfs(1,1,m,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "   \n",
    "        f = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]\n",
    "        print(f)\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                f[i][j] = f[i - 1][j] + f[i][j - 1]\n",
    "        return f[m - 1][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        nums = [[1] * n] + [[1] + [0] * (n-1) for _ in range(m-1)]\n",
    "        print(nums)\n",
    "        for x in range(1, m):\n",
    "            for y in range(1, n):\n",
    "                nums[x][y] = nums[x - 1][y] + nums[x][y - 1]\n",
    "        return nums[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        dp[0][0] = 1 \n",
    "        for i in range(m):\n",
    "            dp[i][0] = 1\n",
    "        for i in range(n):\n",
    "            dp[0][i] = 1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j] = 0\n",
    "                if i >0 :\n",
    "                    dp[i][j] += dp[i-1][j]\n",
    "                if j >0 :\n",
    "                    dp[i][j] +=dp[i][j-1]\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        # 把第一行第一列全部设为1\n",
    "        for j in range(n):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(m):\n",
    "            dp[i][0] = 1\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i][j-1] + dp[i-1][j]\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            dp[i][0] = 1\n",
    "        for j in range(n):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [[1] * n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and j >0:\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "                elif i > 0:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "        return dp[m-1][n-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp  = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            dp[i][0] = 1\n",
    "        for j in range(n):\n",
    "            dp[0][j] = 1\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[m-1][n-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        f=[[0]*n for _ in range(max(m,n))]\n",
    "        print(f)\n",
    "        f[0][0]=1\n",
    "        for i in range(1,m):\n",
    "            f[i][0]=1\n",
    "        for j in range(1,n):\n",
    "            f[0][j]=1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                f[i][j]=f[i-1][j]+f[i][j-1]\n",
    "        return f[m-1][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        dp = [  [0] * (m+1) ] * (n+1)\n",
    "\n",
    "        print(dp)\n",
    "        dp[0][1] = 1\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "                \n",
    "        print(dp)\n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i >= m or j >= n:\n",
    "                return 0\n",
    "            if i == m-1 and j == n-1:\n",
    "                return 1\n",
    "            return dfs(i+1,j) + dfs(i,j+1)\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        return self.pathswithdict(m,n,{})\n",
    "    \n",
    "\n",
    "    def pathswithdict(self, m, n, dict_paths):\n",
    "\n",
    "        if m+n<=3:\n",
    "            return 1\n",
    "        elif (m,n) in dict_paths:\n",
    "            return dict_paths[(m,n)]\n",
    "        else:\n",
    "            if m==1:\n",
    "                dict_paths[(m,n)]=self.pathswithdict(m,n-1,dict_paths)\n",
    "                return self.pathswithdict(m,n-1,dict_paths)\n",
    "            elif n==1:\n",
    "                dict_paths[(m,n)]=self.pathswithdict(m-1,n,dict_paths)\n",
    "                return self.pathswithdict(m-1,n,dict_paths)\n",
    "            else:\n",
    "                dict_paths[(m,n)]=self.pathswithdict(m-1,n,dict_paths)+self.pathswithdict(m,n-1,dict_paths)\n",
    "                return self.pathswithdict(m-1,n,dict_paths)+self.pathswithdict(m,n-1,dict_paths)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
